<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="width=device-width, initial-scale=1">
<style>
    body {
      margin: 0;
      font-family: Arial, Helvetica, sans-serif;
    }

    .topnav {
      overflow: hidden;
      background-color: #333;
    }

    .topnav a {
      float: left;
      color: #f2f2f2;
      text-align: center;
      padding: 14px 16px;
      text-decoration: none;
      font-size: 17px;
    }
    }
</style>
</head>
<body>

<div class="topnav" id = "Navigate">
  <a href="#Intro">Вступление</a>
  <a href="#Terms">Терминология</a>
  <a href="#About">Описание алгоритма</a>
  <a href="#Use">Использование</a>
</div>

<div style="padding-left:16px" id = "Intro">
  <h2>Вступление</h2>
    <p> Дан взвешенный неориентированный граф <i>G</i> с <i>n</i> вершинами и <i>m</i> рёбрами. Требуется найти такое поддерево этого графа, которое бы соединяло все его вершины, и при этом обладало наименьшим возможным весом (т.е. суммой весов рёбер). Поддерево — это набор рёбер, соединяющих все вершины, причём из любой вершины можно добраться до любой другой ровно одним простым путём. </p>

    <p> Такое поддерево называется минимальным остовным деревом или просто <b>минимальным остовом</b>. Легко понять, что любой остов обязательно будет содержать n-1 ребро. </p>

    <p> В естественной постановке эта задача звучит следующим образом: есть n городов, и для каждой пары известна стоимость соеинения их дорогой. Требуется соединить все города так, чтобы можно было доехать из любого города в другой, а при этом стоимость прокладки дорог была бы минимальной.</p>
    <div class="topnav">
        <a href="#Navigate">Вернуться</a>
    </div>
</div>

<div style="padding-left:16px" id = "Terms">
  <h2>Необходимая терминология</h2>
    <p><b>Графом</b> называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.</p>
    <p><b>Связный граф</b> — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.</p>
    <p><b>Неориентированный граф</b> – граф, рёбра которого не имеют определённого направления.</p>
    <p><b>Неориентированный граф</b> называется <b>ациклическим</b>, если в нем отсутствуют циклы (замкнутые обходы без повторного прохода по ребру или посещения вершины дважды, за исключением начальной и конечной вершин).</p>
    <p><b>Остовное дерево</b> — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.</p>
    <div style="padding-left:16px">
     <img src="/home/artjom/Изображения/prim.png" width=550>
    </div>

    <p> Такое поддерево называется минимальным остовным деревом или просто <b>минимальным остовом</b>. Легко понять, что любой остов обязательно будет содержать n-1 ребро. </p>

    <p> В естественной постановке эта задача звучит следующим образом: есть n городов, и для каждой пары известна стоимость соединения их дорогой (либо известно, что соединить их нельзя). Требуется соединить все города так, чтобы можно было доехать из любого города в другой, а при этом стоимость прокладки дорог была бы минимальной.</p>
    <div class="topnav">
        <a href="#Navigate">Вернуться</a>
    </div>
</div>

<div style="padding-left:16px" id = "About">
  <h2>Описание алгоритма</h2>
    <p> Сам алгоритм имеет очень простой вид. Искомый <b>минимальный остов</b> строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов. После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой — наоборот, во всех остальных, кроме этих двух. И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов (если таких рёбер несколько, можно взять любое). Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины (или, что то же самое, n-1 ребро). </P>

    <p> В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет (количество выбранных рёбер останется меньше n-1).</p>
    <div style="padding-left:16px">
     <img src="/home/artjom/Изображения/example.png" width=1950>
    </div>
<div class="topnav">
        <a href="#Navigate">Вернуться</a>
</div>
</div>

<div style="padding-left:16px" id = "Use">
  <h2>Использование</h2>
    <p>Для решенеия задач по типу: есть  городов, и для каждой пары известна стоимость соединения их дорогой (либо известно, что соединить их нельзя). </p>
    <p>Требуется соединить все города так, чтобы можно было доехать из любого города в другой, а при этом стоимость прокладки дорог была бы минимальной — нам нужно найти минимальное остовное дерево.</p>
<div class="topnav">
      <a href="#Navigate">Вернуться</a>
  </div>
</div>

</body>
</html>
